Date: Tue, 26 Nov 1996 18:38:21 GMT
Server: NCSA/1.5.2
Last-modified: Wed, 30 Aug 1995 21:49:48 GMT
Content-type: text/html
Content-length: 2635

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CS 142 Syllabus</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<meta name="description" value="CS 142 Syllabus">
<meta name="keywords" value="syllabus">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
  <CENTER><H3>Computer Science 142 - Theory of Computation</H3></CENTER><P>
Pomona College<BR> Fall Semester, 1995<BR> Mr. Bull<BR>Millikan 210<BR> TTh 9:40<P>
<DL>
<P>
<P><DT><B>Prerequisites:</B><DD>
  The official prerequisite for the course
is an introduction to Computer Science, usually Pomona CS 41 or HMC
CS 60.  It is helpful also to have taken a mathematics course, like
linear algebra, which emphasizes definitions and theorems.  Consult
the instructor if you are uncertain about your preparation.
<P>
<P><DT><B>Textbook:</B><DD>
  Floyd and Beigel, <i>The Language of
Machines:  An Introduction to Computability and Formal Languages,</i>
Computer Science Press, 1994.
<P>
<P><DT><B>Topics:</B><DD>
  The purpose of the course is to understand the
nature of computation by investigating several different models.
Formal languages (including regular languages, context&#173 free languages,
recursive languages, and languages which can be recognized in
polynomial time) and other tools will be used to study the comparative
power of these models.  There will not be enough time to cover the
entire book, but we will include some sections from almost every
chapter.  The central chapters are 4, 5, and 7.
<P>
<P><DT><B>Assignments:</B><DD>
  Written work, mostly problem sets, will be
assigned weekly.  No late work will be accepted, except for illness or
similar reasons.  Normally, 40% of the grade will be determined by
the work on these assignments.  The effect on the grade will be
greater for those who do not turn in the assigned work.
<P>
<P><DT><B>Midterms:</B><DD>
  The two midterms, which together will
account for 35% of the grade, will be on September 28 and November 2.
<P>
<P><DT><B>Final Exam:</B><DD>
  The final exam is scheduled for 8 a.m. on
Tuesday, December 12.  It will contribute toward 25% of the grade.
<P>
<P><DT><B>Office Hours:</B><DD>
  Mondays 1:15-2:30, Tuesdays 11-12,
Fridays 11-12, and by appointment.  Millikan 212&#173 c.  Extension 18709.
<!WA0><A NAME=tex2html1 HREF="mailto:rbull@pomona.edu">Electronic mail: <tt>rbull@pomona.edu</tt></A>
<P>
</DL>
<BR> <HR>
<P><ADDRESS>
<I><!WA1><A HREF="mailto:rbull@pomona.edu">Everett Bull</A><BR>
August 30, 1995</I>
</ADDRESS>
</BODY>
